﻿using System;
using System.Collections.Generic;
using System.Text;
using ExpressionUtil.Exceptions;

namespace ExpressionUtil
{
    /// <summary>
    /// 引用排序器，用于按引用关系排序和检查循环引用
    /// （当前要求所有作为表达式ID的符号和表达式中的符号都不相同）
    /// </summary>
    public class DependencySorter
    {
        /// <summary>
        /// 对指定的表达式进行排序
        /// </summary>
        /// <param name="exps">指定的表达式</param>
        /// <returns>排序后的表达式</returns>
        public static KeyValuePair<string, Expression>[] Sort(Dictionary<string, Expression> exps)
        {
            /*
             * 排序方法：
             * 依次遍历所有表达式中解析出的符号（深度优先方式，在遍历子符号之前先将本身压入堆栈），
             * 直到解析的符号为外部符号为止（在压入堆栈的过程中可能压入重复的符号，详见测试用例TestDependencySorterDirecrCross），
             * 所有符号已入栈之后开始弹出元素，并以此填充数组，之前填入过的符号不再填入。
             */
            Stack<string> stack = new Stack<string>();
            Dictionary<string, Expression> processedExp = new Dictionary<string, Expression>();
            Dictionary<string, string> parentSymbol = new Dictionary<string, string>();
            foreach (KeyValuePair<string, Expression> pair in exps)
            {
                SortCore(exps, pair.Key, stack, parentSymbol);
                parentSymbol.Clear();
            }
            KeyValuePair<string, Expression>[] ret = new KeyValuePair<string, Expression>[exps.Count];
            int index = 0;
            System.Diagnostics.Debug.WriteLine("==================================Start sort order==================================");
            while (stack.Count > 0)
            {
                string expId = stack.Pop();
                if (!processedExp.ContainsKey(expId))
                {
                    ret[index] = new KeyValuePair<string, Expression>(expId, exps[expId]);
                    processedExp.Add(ret[index].Key, ret[index].Value);
                    System.Diagnostics.Debug.WriteLine(string.Format("{0}:{1}", ret[index].Key, ret[index].Value.Expr));
                    index++;
                }
            }
            System.Diagnostics.Debug.WriteLine("==================================End sort order==================================");
            return ret;
        }

        /// <summary>
        /// 排序当前表达式
        /// </summary>
        /// <param name="exps">所有指定排序的表达式</param>
        /// <param name="expName">当前表达式标识</param>
        /// <param name="stack">当前表达式排序堆栈</param>
        /// <param name="parentSymbol">父表达式符号堆栈</param>
        private static void SortCore(Dictionary<string, Expression> exps,
            string expName,
            Stack<string> stack,
            Dictionary<string, string> parentSymbol)
        {
            if (parentSymbol.ContainsKey(expName))
            {
                //检查循环引用，如果直接或间接引用自己（即当前节点是父亲节点或祖先节点），就......
                Expression errExp = exps[expName];
                string msg = string.Format("Circular reference has been found,symbol:{0},expression:{1}.", expName, errExp.Expr);
                throw new CircularReferenceException(msg);
            }
            if (!exps.ContainsKey(expName))
            {
                //如果为外部符号，则跳过该符号并继续处理下一个
                return;
            }
            Expression exp = exps[expName];
            string[] names = exp.VariableSymbols;
            stack.Push(expName);
            parentSymbol.Add(expName, expName);//加入父节点集合，用于检查循环引用
            for (int i = 0; i < names.Length; i++)
            {
                SortCore(exps, names[i], stack, parentSymbol);
            }
            parentSymbol.Remove(expName);
        }
    }
}
